/**
 * Created with IntelliJ IDEA.
 * User:xieChao
 * Date:2022/10/25 12:34
 */
public class HashBuck {
    private static class Node{
        private int key;
        private int value;
        Node next;

        public Node(int key,int value){
            this.key = key;
            this.value = value;
        }
    }

    private Node[] array;
    private int size;
    private static final double LOAD_FACTOR = 0.75;//负载因子

    /**
     * 给定初始容量，不然会空指针异常
     */
    public HashBuck(){
        this.array = new Node[10];
    }

    public int put(int key,int value){
        int index = key % array.length;

        for (Node cur = array[index];cur != null;cur = cur.next){
            if(key == cur.key){
                int oldValue = cur.value;
                cur.value = value;
                return oldValue;
            }
        }
        //如果没有找到就插入新节点
        Node node = new Node(key, value);
        //头插
        node.next = array[index];
        array[index] = node;
        size++;

        if(loadFactor() >= LOAD_FACTOR){
            resize();
        }
        return -1;
    }

    /**
     * 扩容操作
     */
    private void resize(){
        Node[] newArray = new Node[array.length*2];
        for (int i = 0; i < array.length; i++) {
            //遍历原来的表，重新插入扩容的新表
            for(Node cur = array[i];cur != null;cur = cur.next){
                int index = cur.key % newArray.length;
                //头插
                cur.next = newArray[index];
                newArray[index] = cur;
            }
        }
        array = newArray;
    }

    /**
     *计算负载因子
     * @return
     */
    private double loadFactor(){
        return 1.0*size/ array.length;
    }


    public int get(int key){
        int index = key % array.length;

        Node head = array[index];
        for(Node cur = head;cur != null;cur = cur.next){
            if(key == cur.key){
                return cur.value;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        HashBuck hashBuck = new HashBuck();
        hashBuck.put(10,0);
        hashBuck.put(11,11);
        hashBuck.put(12,12);
        hashBuck.put(13,13);
        hashBuck.put(14,14);
        hashBuck.put(4,14);
        hashBuck.put(8,18);
        hashBuck.put(19,19);
        System.out.println(hashBuck.get(19));

    }



}
